package backtrack;

public class _14_37_解数独 {
    public void solveSudoku(char[][] board) {
    	
    	backtracking(board);
    	
    }
    public boolean backtracking(char[][] board) {
    	// 行
    	for(int i = 0; i < board.length; i++) {
    		// 列
    		for(int j = 0; j < board.length; j++) {
    			// 遇到有值则跳过
    			if(board[i][j] != '.') {
    				continue;
    			}
    			// 使用不同数字填充
    			for(char k = '1'; k <= '9'; k++) {
    				// 判断填充的数字是否符合规则
    				if(check(i, j, k, board)) {
    					board[i][j] = k;
    					// 递归 如果返回的是true说明已经填满棋盘，既然填满棋盘，说明所有的数字都符合要求
    					if(backtracking(board)) {
    						return true;
    					}
    					board[i][j] = '.';
    				}
    			}
    			return false;
    		}
    	}
    	
    	
    	return true;
    }
    public boolean check(int row, int col, char num, char[][] board) {
    	
    	for(int i = 0; i < board.length; i++) {
    		if(board[row][i] == num) {
    			return false;
    		}
    	}
    	
    	for(int i = 0; i < board.length; i++) {
    		if(board[i][col] == num) {
    			return false;
    		}
    	}
    	
    	int startRow = (row / 3) * 3;
    	int startCol = (col / 3) * 3;
    	for(int i = startRow; i < startRow + 3; i++) {
    		for(int j = startCol; j < startCol + 3; j++) {
    			if(board[i][j] == num) {
    				return false;
    			}
    		}
    	}
    	
    	return true;
    }
    
    public static void main(String[] args) {
    	char[][] board = {{'5','3','.','.','7','.','.','.','.'},
    					  {'6','.','.','1','9','5','.','.','.'},
    					  {'.','9','8','.','.','.','.','6','.'},
    					  {'8','.','.','.','6','.','.','.','3'},
    					  {'4','.','.','8','.','3','.','.','1'},
    					  {'7','.','.','.','2','.','.','.','6'},
    					  {'.','6','.','.','.','.','2','8','.'},
    					  {'.','.','.','4','1','9','.','.','5'},
    					  {'.','.','.','.','8','.','.','7','9'}};
    	new _14_37_解数独().solveSudoku(board);
    	
    	for(int i = 0; i < board.length; i++) {
    		for(int j = 0; j < board.length; j++) {
    			System.out.print(board[i][j] + " ");
    		}
    		System.out.println();
    	}
	}
}
